package com.gitee.feizns.explore.data_structure.linked_list.singly.reverse_between;

/**
 * 反转链表 II
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 * @author feizns
 * @since 2019/10/29
 */
public class Main {

    private static ListNode create() {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);
        node.next.next.next.next.next = new ListNode(6);
        node.next.next.next.next.next.next = new ListNode(7);
        return node;
    }

    public static void main(String[] args) {
        ListNode node = create();
        reverseBetween(node, 1, 5).print();
    }

    public static ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode prev = null;
        ListNode curt = head;
        ListNode tail = null;
        ListNode mH = null;
        for (int i = 1; curt != null; i++) {
            ListNode next = curt.next;
            if ( i == m - 1 )
                mH = curt;
            else if ( i == m )
                tail = curt;
            else if ( i > m && i < n )
                curt.next = prev;
            else if ( i == n ) {
                curt.next = prev;
                tail.next = next;
                if ( mH != null ) {
                    mH.next = curt;
                    return head;
                } else {
                    return curt;
                }
            }
            prev = curt;
            curt = next;
        }
        return head;
    }

}
